package net.tp.algo.sort;

import java.util.Arrays;

import net.tp.algo.heap.IntervalHeap;

/**
 * 
 * <p>External in-place quick sort.</p>
 * 
 *
 * @author Trung Phan
 *
 */
public class ExternalQuickSort {

	public static void sort(int capacity, int[] data) {
		sort(capacity, data, 0, data.length - 1);
	}
	
	private static void sort(int capacity, int[] data, int lo, int hi) {
		
		while (hi - lo > capacity) {
			
			int a = lo + capacity / 2;
			int b = hi - capacity / 2;
			int lt = lo;
			int gt = hi;
			
			Integer[] pivot = new Integer[hi-lo - (b - a)];
			for (int i = lo; i < a; i++) {
				pivot[i-lo] = data[i];
			}
			for (int i = hi; i > b; i--) {
				pivot[i-lo-(b-a)-1] = data[i];
			}
			IntervalHeap<Integer> heap = new IntervalHeap<>(pivot);
			
			boolean left = true;
			while (a <= b) {
				int element = left ? data[a++] : data[b--];
				
				if (element < heap.min()) {
					data[lt++] = element;
					left = true;
				}
				else if (element > heap.max()) {
					data[gt--] = element;
					left = false;
				}
				else if (element > heap.min() || element < heap.max()) {
					left = !left; // alternate
					if (left) {
						data[lt++] = heap.removeMin();
					}
					else {
						data[gt--] = heap.removeMax();
					}
					heap.add(element);
				}
				else if (element > heap.min()) {
					data[lt++] = heap.removeMin();
					heap.add(element);
					left = true;
				}
				else if (element < heap.max()) {
					data[gt--] = heap.removeMax();
					heap.add(element);
					left = false;
				}
				else {
					if (left) {
						data[lt++] = element;
					}
					else {
						data[gt--] = element;
					}
				}
			}
			
			for (int i = lt; i <= gt; i++) {
				data[i] = heap.removeMin();
			}
			
			if (hi - gt < lt - lo) {
				sort(capacity, data, gt+1, hi);
				hi = lt-1;
			}
			else {
				sort(capacity, data, lo, lt-1);
				lo = gt+1;
			}
			
		}
		
		if (lo <= hi) {
			Integer[] temp = new Integer[hi - lo + 1];
			for (int i = lo; i <= hi; i++) {
				temp[i-lo] = data[i];
			}
			IntervalHeap<Integer> heap = new IntervalHeap<>(temp);
			for (int i = lo; i <= hi; i++) {
				data[i] = heap.removeMin();
			}
		}
		
	}
	
	public static void main(String ...strings) {
		
		int[] data = {4, 2, 1, 6, 9, 3, 5, 7, 8, 10, 0, 15, 13};
		
		sort(4, data);
		
	}
	
	
}
